#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int f=0,t=0;
    char c=getchar();
    while(!isdigit(c)) t|=(c=='-'),c=getchar();
    while(isdigit(c)) f=(f<<3)+(f<<1)+c-48,c=getchar();
    return t?-f:f;
}
void write(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar('0'+x%10);
}
struct f{int x,y;}a[25];
int pd[14][15],pd1[15][15];
int cnt[25],ans=1e18,jl[25],cnt1[25];
int b[25],top,n1;
void dfs1(int p,int n,int sum){
	if(p==n){
		for(int i=0;i<n;i++){
			int u=b[cnt1[i]],v=b[cnt1[(i+1)%n]];
			pd1[u][v]=1;
		}int pdd=0;
		for(int i=1;i<=n1;i++){
			for(int j=1;j<=n1;j++){
				if(pd[i][j]!=pd1[i][j]) pdd=1;
			}
		}
		if(pdd==0) ans=min(ans,sum);
		for(int i=0;i<n;i++){
			int u=b[cnt1[i]],v=b[cnt1[(i+1)%n]];
			pd1[u][v]=0;
		}
		return;
	}
	for(int i=1;i<=n;i++){if(jl[i]==0){jl[i]=1;cnt1[p]=i;dfs1(p+1,n,sum);jl[i]=0;}}
}
void dfs(int p,int n,int m){
	if(p>n){
		int sum=0;top=0;
		for(int i=1;i<=n;i++){if(cnt[i]!=i) sum++;else b[++top]=i;}
		for(int i=1;i<=m;i++){pd[cnt[a[i].x]][cnt[a[i].y]]=1;}
		dfs1(0,n-sum,sum);
		for(int i=1;i<=m;i++){pd[cnt[a[i].x]][cnt[a[i].y]]=0;}
		return;
	}
	for(int i=1;i<=n;i++) cnt[p]=i,dfs(p+1,n,m);
}
signed main(){
	freopen("circ.in","r",stdin);
	freopen("circ.out","w",stdout);
	int t=read();
	while(t--){ans=1e18;
		int n=read(),m=read();n1=n;
		for(int i=1;i<=m;i++){a[i].x=read()+1,a[i].y=1+read();}
		dfs(1,n,m);
		write(ans),cout<<'\n';
	} 
	return 0;
}
